package java学习.leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.*;
import java.util.logging.Level;

/**
 * @author 刘世锦
 * 2022-12-13 23:35:56	 当前时间
 */
//给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 
//
// 叶子节点 是指没有子节点的节点。 
//
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//输出：[[5,4,11,2],[5,8,4,5]]
// 
//
// 示例 2： 
//
// 
//输入：root = [1,2,3], targetSum = 5
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：root = [1,2], targetSum = 0
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点总数在范围 [0, 5000] 内 
// -1000 <= Node.val <= 1000 
// -1000 <= targetSum <= 1000 
// 
// 
// 
// Related Topics 树 深度优先搜索 回溯 二叉树 
// 👍 874 👎 0

public class 路径总和II{
	public static void main(String[] args) {
		Solution solution = new 路径总和II().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

	/** 复习  @author 刘世锦
	 *  @date  2023/2/2 11:12
	 *
	 *  _ 5_
	 *
	 *  _ _
	 *
	 *  _ _
	 *
	 */
	// 递归
	public List<List<Integer>>  pathSum(TreeNode root, int targetSum) {
		List<List<Integer>> list = new ArrayList<>();
		if (root!=null){
			dfsByReview(root,root.val,targetSum,list,new ArrayList<>());
		}
		return  list;
	}

	private void dfsByReview(TreeNode node,int sum, int targetSum, List<List<Integer>> list,List<Integer> path) {
		// 先添加元素
		path.add(node.val);
		// 到叶子结点
		if (node.left==null&&node.right==null&&sum==targetSum){
			list.add(new ArrayList<>(path));
		}

		if (node.left!=null){
			dfsByReview(node.left,sum+node.left.val,targetSum,list,path);
			path.remove(path.size()-1);
		}
		if (node.right!=null){
			dfsByReview(node.right,sum+node.right.val,targetSum, list,path);
			path.remove(path.size()-1);
		}


	}

	public List<List<Integer>>  pathSum2(TreeNode root, int targetSum) {
		List<List<Integer>> list = new ArrayList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		Queue<String> queueString = new LinkedList<>();
		if (root!=null){
			queue.offer(root);
			queueString.offer(root.val+"");
			while (!queue.isEmpty()){
				int size = queue.size();
				for (int i = 0; i < size; i++) {
					TreeNode node = queue.poll();
					String nodeString = queueString.poll();
					// 叶子节点
					if (node.val==targetSum&&node.left==null&&node.right==null){
//						System.out.println(nodeString);
						ArrayList<Integer> item = new ArrayList<>();
						String[] strings = nodeString.split(",");
						for (String string : strings) {
							item.add(Integer.parseInt(string));
						}
						list.add(item);
					}
					if (node.left!=null){
						queueString.offer(nodeString+","+node.left.val);
						node.left.val+=node.val;
						queue.offer(node.left);
					}
					if (node.right!=null){
						queueString.offer(nodeString+","+node.right.val);
						node.right.val+=node.val;
						queue.offer(node.right);
					}
				}

			}



		}

		return list;

	}





	// 复习end

	/**
	 * 递归：体现回溯的好写法：
	 */
	public List<List<Integer>> pathSumDFS(TreeNode root, int targetSum) {
		List<List<Integer>> resList = new ArrayList<>();
		ArrayList<Integer> list = new ArrayList<>();
		if (root!=null){
			dfsTraverse(root,list,resList,0,targetSum);
		}
		return resList;
	}

	private void dfsTraverse(TreeNode root, ArrayList<Integer> list, List<List<Integer>> resList, int num, int targetSum) {
		// add元素
		list.add(root.val);
		num+=root.val;
		if (root.left==null&&root.right==null){
			// 叶子节点+符合targetSum 加入 resList
			if (num==targetSum){
				/**
				 *  防止 list的值被修改 详见 dfs(root,list,resList,0,targetSum);
				 */
				resList.add(new ArrayList<>(list));
			}
		}
		if (root.left!=null){
			dfsTraverse(root.left,list,resList,num,targetSum);
			//  回溯: 上一行递归进去后,path中添加了左孩子结点;此时想继续走右边路径,当然要回退到根结点(remove path中最后一个结点即可)
			list.remove(list.size()-1); // 回溯
		}
		if (root.right!=null){
			dfsTraverse(root.right,list,resList,num,targetSum);
			list.remove(list.size()-1); // 回溯
		}

	}


	public List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
		List<List<Integer>> resList = new ArrayList<>();
		ArrayList<Integer> list = new ArrayList<>();
		dfs(root,list,resList,0,targetSum);
		return resList;

	}

	private void dfs(TreeNode root, List<Integer> list, List<List<Integer>> resList,int num,int targetSum) {
		if (root==null){
			return;
		}
		num+=root.val;
		list.add(root.val);
		if (root.left==null&&root.right==null){
			if (num==targetSum){
				/**
				 * 为什么用resList.add(list); 就不行？
				 *  因为 现在添加到resList的 list 在后续 递归遍历到其他树分支时，会在该list的基础上改动。（Java中，list引用 一直指向的是同一地址）
				 *  故需要隔离开
				 */
				resList.add(new ArrayList<>(list));
			}
		}
		dfs(root.left,list,resList,num,targetSum);
		dfs(root.right,list,resList,num,targetSum);
		// 回溯，遍历完左分支后，去除左叶子节点，开始右分支。
		list.remove(list.size()-1);
	}

	/**
	 * 最容易想到的方法：
	 */
	public List<List<Integer>> pathSumBFS1(TreeNode root, int targetSum) {
		List<List<Integer>> resList = new ArrayList<>();
		LinkedList<TreeNode> nodeQueue = new LinkedList<>(); // 横向遍历节点
		LinkedList<Integer> nodeValQueue = new LinkedList<>(); // 用来判断 不同分支的总和
		LinkedList<String> stringQueue = new LinkedList<>();  // 记录每个分支 String
		if (root!=null){
			nodeQueue.offer(root);
			nodeValQueue.offer(root.val);
			stringQueue.offer(root.val+"");
			while (!nodeQueue.isEmpty()){
				ArrayList<Integer> item = new ArrayList<>();
				TreeNode node = nodeQueue.poll();
				Integer nodeVal = nodeValQueue.poll();
				String nodeString = stringQueue.poll();
				if (node.left==null&&node.right==null){
					if (nodeVal==targetSum){
						// 拿String 存储 效率低
						String[] split = nodeString.split("->");
						for (String s : split) {
							item.add(Integer.parseInt(s));
						}
						resList.add(item);
					}
				}
				if (node.left!=null){
					nodeQueue.offer(node.left);
					nodeValQueue.offer(nodeVal+node.left.val);
					stringQueue.offer(nodeString+"->"+node.left.val);
				}
				if (node.right!=null){
					nodeQueue.offer(node.right);
					nodeValQueue.offer(nodeVal+node.right.val);
					stringQueue.offer(nodeString+"->"+node.right.val);
				}
			}
		}
		return resList;
	}

	/**
	 *  上面拿 String存储，改进：拿List<> 存
	 *  使用list存储 需要 注意回溯问题
	 */
	public List<List<Integer>> pathSumBFS2(TreeNode root, int targetSum) {
		List<List<Integer>> resList = new ArrayList<>();
		LinkedList<TreeNode> nodeQueue = new LinkedList<>();
		LinkedList<Integer> nodeValQueue = new LinkedList<>();
		LinkedList<List<Integer>> listQueue = new LinkedList<>();
		if (root!=null){
			nodeQueue.offer(root);
			nodeValQueue.offer(root.val);
			List<Integer> item = new ArrayList<>();
			item.add(root.val);
			listQueue.add(item);
			while (!nodeQueue.isEmpty()){
				TreeNode node = nodeQueue.poll();
				Integer nodeVal = nodeValQueue.poll();
				List<Integer> nodeList = listQueue.poll();
				if (node.left==null&&node.right==null){
					if (nodeVal==targetSum){
						resList.add(nodeList);
					}
				}
				if (node.left!=null){
					nodeQueue.offer(node.left);
					nodeValQueue.offer(nodeVal+node.left.val);
					nodeList.add(node.left.val);
					listQueue.offer(new ArrayList<>(nodeList));
					nodeList.remove(nodeList.size()-1);// 回溯，开始右分支
				}
				if (node.right!=null){
					nodeQueue.offer(node.right);
					nodeValQueue.offer(nodeVal+node.right.val);
					nodeList.add(node.right.val);
					listQueue.offer(new ArrayList<>(nodeList));

				}
			}
		}
		return resList;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
